/*
	2020/07/05 17:27:09
	代码无BUG
	KMP算法
*/

#include <iostream>
#define MAXSIZE 20
using namespace std;

typedef struct
{
	char str[MAXSIZE];
	int length;
} Str;

//生成next
void getNext(Str substr, int next[])
{
	int i = 1, j = 0;
	next[i] = 0;
	while (i < substr.length)
	{
		if (j == 0 || substr.str[i] == substr.str[j])
		{
			++i;
			++j;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}
	}
}

int KMP(Str str, Str substr, int next[])
{
	int i = 1, j = 1;
	while (i <= str.length && j <= substr.length)
	{
		if (j == 0 || str.str[i] == substr.str[j])
		{
			++i;
			++j;
		}
		else
			j = next[j];
	}
	if (j > substr.length)
		return i - substr.length;
	else
		return -1;
}

int main(void)
{
	Str s1,s2;
	s1.length = 0;
	s2.length = 0;
	char a[] = "ABAABABBAABBABAN";
	char b[] = "BABA";

	int i = 0;
	while(a[i++] != '\0')
	{
		s1.str[i] = a[i - 1];
		++s1.length;
	}
	i = 0;
	while(b[i++] != '\0')
	{
		s2.str[i] = b[i - 1];
		++s2.length;
	}
	cout << s1.length << " " << s2.length << endl;
	int next[4];
	getNext(s2, next);
	cout << KMP(s1,s2,next) << endl;
	cout << "hello world!" << endl;
	return 0;
}



